

/**
 * 
 * 判断一个链表是否为回文结构
 * 
 * 描述

给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 
0
≤
n
≤
1
0
5
0≤n≤10 
5
 ，链表中每个节点的值满足 
∣
v
a
l
∣
≤
1
0
7
∣val∣≤10 
7
 
示例1

输入：
{1}
复制
返回值：
true
复制
示例2

输入：
{2,1}
复制
返回值：
false
复制
说明：
2->1     
示例3

输入：
{1,2,2,1}
复制
返回值：
true
复制
说明：
1->2->2->1     
 */
public class 判断一个链表是否为回文结构 {
    
    public static void main(String[] args) {
        
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(2);
        node.next.next.next = new ListNode(1);
        node.next.next.next.next = new ListNode(5);

        boolean result = isPail(node);

        System.err.println(result);
        
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public static boolean isPail (ListNode head) {
        // write code here

        if (head == null || head.next == null) {
            return true;
        }
        // 找到链表的中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!= null && fast.next.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondHalf = slow.next;
        slow.next = null;
        // 反转后半部分链表
        ListNode reversedSecondHalf = reverseList(secondHalf);
        // 比较前半部分和反转后的后半部分
        ListNode p1 = head;
        ListNode p2 = reversedSecondHalf;
        boolean isPalindrome = true;
        while (p2!= null) {
            if (p1.val!= p2.val) {
                isPalindrome = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 恢复链表原状（可选）
        slow.next = reverseList(reversedSecondHalf);
        return isPalindrome;
    }

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr!= null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
}
